<!DOCTYPE html>
<html lang="zh-CN" data-theme="light">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width,initial-scale=1" />
    <meta name="generator" content="VuePress 2.0.0-beta.46" />
    <meta name="theme" content="VuePress Theme Hope" />
    <title>算法题：切木头 | 你好，戴先生</title><meta name="description" content="无论何时归来，我都是少年">
    <style>
      :root {
        --bg-color: #fff;
      }

      html[data-theme="dark"] {
        --bg-color: #1d2025;
      }

      html,
      body {
        background-color: var(--bg-color);
      }
    </style>
    <script>
      const userMode = localStorage.getItem("vuepress-theme-hope-scheme");
      const systemDarkMode =
        window.matchMedia &&
        window.matchMedia("(prefers-color-scheme: dark)").matches;

      if (userMode === "dark" || (userMode !== "light" && systemDarkMode)) {
        document.querySelector("html").setAttribute("data-theme", "dark");
      }
    </script>
    <link rel="stylesheet" href="/assets/style.4bad6894.css">
    <link rel="modulepreload" href="/assets/app.cfbcad7e.js"><link rel="modulepreload" href="/assets/cut_wood.html.01709a45.js"><link rel="modulepreload" href="/assets/plugin-vue_export-helper.21dcd24c.js"><link rel="modulepreload" href="/assets/cut_wood.html.9fd1cd06.js"><link rel="prefetch" href="/assets/index.html.0c572205.js"><link rel="prefetch" href="/assets/index.html.f1523c68.js"><link rel="prefetch" href="/assets/index.html.b2ad61dc.js"><link rel="prefetch" href="/assets/index.html.47e2ecb8.js"><link rel="prefetch" href="/assets/index.html.6d9d68c0.js"><link rel="prefetch" href="/assets/why-hr-increase-income-through-tax-avoidance.html.231f1482.js"><link rel="prefetch" href="/assets/sanding_in_front_of_the_30-year-old_door.html.3b1e82a4.js"><link rel="prefetch" href="/assets/shylock-on-the-plain.html.4e5ecda6.js"><link rel="prefetch" href="/assets/celadon.html.a44f776e.js"><link rel="prefetch" href="/assets/search-in-rotated-sorted-array.html.3163bc5a.js"><link rel="prefetch" href="/assets/digital-huorongdao-of-java.html.43857b67.js"><link rel="prefetch" href="/assets/404.html.a8e3cb07.js"><link rel="prefetch" href="/assets/index.html.e845cdce.js"><link rel="prefetch" href="/assets/index.html.ff7ccc29.js"><link rel="prefetch" href="/assets/index.html.d4953529.js"><link rel="prefetch" href="/assets/index.html.fb619bb8.js"><link rel="prefetch" href="/assets/index.html.55b4865a.js"><link rel="prefetch" href="/assets/index.html.05f66ce3.js"><link rel="prefetch" href="/assets/index.html.436433ee.js"><link rel="prefetch" href="/assets/index.html.50862118.js"><link rel="prefetch" href="/assets/index.html.b0bc4906.js"><link rel="prefetch" href="/assets/index.html.71820a22.js"><link rel="prefetch" href="/assets/index.html.92ca49fa.js"><link rel="prefetch" href="/assets/index.html.089989f4.js"><link rel="prefetch" href="/assets/index.html.b66adeb3.js"><link rel="prefetch" href="/assets/index.html.309e9ed5.js"><link rel="prefetch" href="/assets/index.html.2162ce1d.js"><link rel="prefetch" href="/assets/index.html.31f2f2dc.js"><link rel="prefetch" href="/assets/index.html.af54eccb.js"><link rel="prefetch" href="/assets/index.html.0dfd5a25.js"><link rel="prefetch" href="/assets/index.html.94b41066.js"><link rel="prefetch" href="/assets/index.html.f84ad2ce.js"><link rel="prefetch" href="/assets/index.html.01f47b74.js"><link rel="prefetch" href="/assets/index.html.68c28b90.js"><link rel="prefetch" href="/assets/why-hr-increase-income-through-tax-avoidance.html.66566d6e.js"><link rel="prefetch" href="/assets/sanding_in_front_of_the_30-year-old_door.html.962bb15c.js"><link rel="prefetch" href="/assets/shylock-on-the-plain.html.08c82b0b.js"><link rel="prefetch" href="/assets/celadon.html.1fe63bd9.js"><link rel="prefetch" href="/assets/search-in-rotated-sorted-array.html.6c507561.js"><link rel="prefetch" href="/assets/digital-huorongdao-of-java.html.30d7d204.js"><link rel="prefetch" href="/assets/404.html.2630f66e.js"><link rel="prefetch" href="/assets/index.html.29702eba.js"><link rel="prefetch" href="/assets/index.html.a26bab7c.js"><link rel="prefetch" href="/assets/index.html.a0ef77bf.js"><link rel="prefetch" href="/assets/index.html.38389937.js"><link rel="prefetch" href="/assets/index.html.9f26b4d5.js"><link rel="prefetch" href="/assets/index.html.c846c020.js"><link rel="prefetch" href="/assets/index.html.5a4029cb.js"><link rel="prefetch" href="/assets/index.html.775c7a70.js"><link rel="prefetch" href="/assets/index.html.e1b7a51c.js"><link rel="prefetch" href="/assets/index.html.89bbbe87.js"><link rel="prefetch" href="/assets/index.html.d71ee1d7.js"><link rel="prefetch" href="/assets/index.html.649acbe9.js"><link rel="prefetch" href="/assets/index.html.428f48b3.js"><link rel="prefetch" href="/assets/index.html.26cb15ba.js"><link rel="prefetch" href="/assets/index.html.5f5de50f.js"><link rel="prefetch" href="/assets/index.html.ee73863b.js"><link rel="prefetch" href="/assets/index.html.6db9f268.js"><link rel="prefetch" href="/assets/404.60b585e2.js"><link rel="prefetch" href="/assets/Layout.8dd7a7a4.js"><link rel="prefetch" href="/assets/Slide.1dd1408d.js"><link rel="prefetch" href="/assets/Blog.f9717e6e.js"><link rel="prefetch" href="/assets/auto.esm.36809f22.js"><link rel="prefetch" href="/assets/index.5cb56ef7.js"><link rel="prefetch" href="/assets/index.1842ee54.js"><link rel="prefetch" href="/assets/mermaid.esm.min.95aabeb7.js"><link rel="prefetch" href="/assets/highlight.esm.d982e650.js"><link rel="prefetch" href="/assets/markdown.esm.832a189d.js"><link rel="prefetch" href="/assets/math.esm.a3f84b6f.js"><link rel="prefetch" href="/assets/notes.esm.3c361cb7.js"><link rel="prefetch" href="/assets/reveal.esm.b96f05d8.js"><link rel="prefetch" href="/assets/search.esm.80da4a02.js"><link rel="prefetch" href="/assets/zoom.esm.8514a202.js"><link rel="prefetch" href="/assets/photoswipe.esm.92018b73.js">
  </head>
  <body>
    <div id="app"><!--[--><!--[--><!--[--><span tabindex="-1"></span><a href="#main-content" class="skip-link sr-only">Skip to content</a><!--]--><div class="theme-container has-toc"><!--[--><!--[--><header class="navbar"><div class="navbar-left"><button class="toggle-sidebar-button" title="Toggle Sidebar"><span class="icon"></span></button><!----><a href="/" class="brand"><img class="logo" src="/images/logo.svg" alt="你好，戴先生"><!----><span class="site-name hide-in-pad">你好，戴先生</span></a><!----></div><div class="navbar-center"><!----><nav class="nav-links"><div class="nav-item hide-in-mobile"><a href="/essay/" class="nav-link" aria-label="戴言泛滥"><span class="icon iconfont icon-edit" style=""></span>戴言泛滥<!----></a></div><div class="nav-item hide-in-mobile"><a href="/tech/" class="nav-link active" aria-label="技术人生"><span class="icon iconfont icon-java" style=""></span>技术人生<!----></a></div><div class="nav-item hide-in-mobile"><a href="/movie/" class="nav-link" aria-label="影视推荐"><span class="icon iconfont icon-actions" style=""></span>影视推荐<!----></a></div><div class="nav-item hide-in-mobile"><a href="/me/" class="nav-link" aria-label="关于作者"><span class="icon iconfont icon-people" style=""></span>关于作者<!----></a></div></nav><!----></div><div class="navbar-right"><!----><div class="nav-item"><!----></div><!----><div class="nav-item hide-in-mobile"><button id="appearance-switch"><svg xmlns="http://www.w3.org/2000/svg" class="icon auto-icon" viewbox="0 0 1024 1024" fill="currentColor" aria-label="auto icon" style="display:block;"><path d="M512 992C246.92 992 32 777.08 32 512S246.92 32 512 32s480 214.92 480 480-214.92 480-480 480zm0-840c-198.78 0-360 161.22-360 360 0 198.84 161.22 360 360 360s360-161.16 360-360c0-198.78-161.22-360-360-360zm0 660V212c165.72 0 300 134.34 300 300 0 165.72-134.28 300-300 300z"></path></svg><svg xmlns="http://www.w3.org/2000/svg" class="icon dark-icon" viewbox="0 0 1024 1024" fill="currentColor" aria-label="dark icon" style="display:none;"><path d="M524.8 938.667h-4.267a439.893 439.893 0 0 1-313.173-134.4 446.293 446.293 0 0 1-11.093-597.334A432.213 432.213 0 0 1 366.933 90.027a42.667 42.667 0 0 1 45.227 9.386 42.667 42.667 0 0 1 10.24 42.667 358.4 358.4 0 0 0 82.773 375.893 361.387 361.387 0 0 0 376.747 82.774 42.667 42.667 0 0 1 54.187 55.04 433.493 433.493 0 0 1-99.84 154.88 438.613 438.613 0 0 1-311.467 128z"></path></svg><svg xmlns="http://www.w3.org/2000/svg" class="icon light-icon" viewbox="0 0 1024 1024" fill="currentColor" aria-label="light icon" style="display:none;"><path d="M952 552h-80a40 40 0 0 1 0-80h80a40 40 0 0 1 0 80zM801.88 280.08a41 41 0 0 1-57.96-57.96l57.96-58a41.04 41.04 0 0 1 58 58l-58 57.96zM512 752a240 240 0 1 1 0-480 240 240 0 0 1 0 480zm0-560a40 40 0 0 1-40-40V72a40 40 0 0 1 80 0v80a40 40 0 0 1-40 40zm-289.88 88.08-58-57.96a41.04 41.04 0 0 1 58-58l57.96 58a41 41 0 0 1-57.96 57.96zM192 512a40 40 0 0 1-40 40H72a40 40 0 0 1 0-80h80a40 40 0 0 1 40 40zm30.12 231.92a41 41 0 0 1 57.96 57.96l-57.96 58a41.04 41.04 0 0 1-58-58l58-57.96zM512 832a40 40 0 0 1 40 40v80a40 40 0 0 1-80 0v-80a40 40 0 0 1 40-40zm289.88-88.08 58 57.96a41.04 41.04 0 0 1-58 58l-57.96-58a41 41 0 0 1 57.96-57.96z"></path></svg></button></div><form class="search-box" role="search"><input type="search" placeholder="搜索内容" autocomplete="off" spellcheck="false" value><!----></form><!----><button class="toggle-navbar-button" aria-label="Toggle Navbar" aria-expanded="false" aria-controls="nav-screen"><span class="button-container"><span class="button-top"></span><span class="button-middle"></span><span class="button-bottom"></span></span></button></div></header><!----><!--]--><!----><div class="toggle-sidebar-wrapper"><span class="arrow left"></span></div><aside class="sidebar"><!--[--><!----><!--]--><ul class="sidebar-links"><li><!--[--><section class="sidebar-group"><p class="sidebar-heading active"><span class="icon iconfont icon-add" style=""></span><span class="title">做做算法</span><!----></p><ul class="sidebar-links"><li><!--[--><a href="/tech/algorithm/search-in-rotated-sorted-array.html" class="nav-link sidebar-link sidebar-page" aria-label="必会算法：在旋转有序的数组中搜索"><!---->必会算法：在旋转有序的数组中搜索<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li><li><!--[--><a aria-current="page" href="/tech/algorithm/cut_wood.html" class="router-link-active router-link-exact-active nav-link active sidebar-link sidebar-page active" aria-label="算法题：切木头"><!---->算法题：切木头<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/tech/algorithm/cut_wood.html#问题1" class="router-link-active router-link-exact-active nav-link sidebar-link heading" aria-label="问题1"><!---->问题1<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/tech/algorithm/cut_wood.html#解题思路" class="router-link-active router-link-exact-active nav-link sidebar-link heading" aria-label="解题思路"><!---->解题思路<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/tech/algorithm/cut_wood.html#代码实现" class="router-link-active router-link-exact-active nav-link sidebar-link heading" aria-label="代码实现"><!---->代码实现<!----></a><ul class="sidebar-sub-headers"></ul></li></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/tech/algorithm/cut_wood.html#问题2" class="router-link-active router-link-exact-active nav-link sidebar-link heading" aria-label="问题2"><!---->问题2<!----></a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a aria-current="page" href="/tech/algorithm/cut_wood.html#解题思路-1" class="router-link-active router-link-exact-active nav-link sidebar-link heading" aria-label="解题思路"><!---->解题思路<!----></a><ul class="sidebar-sub-headers"></ul></li><li class="sidebar-sub-header"><a aria-current="page" href="/tech/algorithm/cut_wood.html#代码实现-1" class="router-link-active router-link-exact-active nav-link sidebar-link heading" aria-label="代码实现"><!---->代码实现<!----></a><ul class="sidebar-sub-headers"></ul></li></ul></li></ul><!--]--></li></ul></section><!--]--></li><li><!--[--><section class="sidebar-group"><p class="sidebar-heading"><span class="icon iconfont icon-config" style=""></span><span class="title">搭搭环境</span><!----></p><ul class="sidebar-links"></ul></section><!--]--></li><li><!--[--><section class="sidebar-group"><p class="sidebar-heading"><span class="icon iconfont icon-code" style=""></span><span class="title">敲敲代码</span><!----></p><ul class="sidebar-links"><li><!--[--><a href="/tech/code/digital-huorongdao-of-java.html" class="nav-link sidebar-link sidebar-page" aria-label="曹操哪里跑！--Java语言实现数字华容道游戏"><!---->曹操哪里跑！--Java语言实现数字华容道游戏<!----></a><ul class="sidebar-sub-headers"></ul><!--]--></li></ul></section><!--]--></li></ul><!--[--><!----><!--]--></aside><!--[--><main class="page" id="main-content"><!--[--><!----><nav class="breadcrumb disable"></nav><div class="page-title"><h1><!---->算法题：切木头</h1><div class="page-info"><span class="author-info" aria-label="作者🖊" data-balloon-pos="down" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon author-icon" viewbox="0 0 1024 1024" fill="currentColor" aria-label="author icon"><path d="M649.6 633.6c86.4-48 147.2-144 147.2-249.6 0-160-128-288-288-288s-288 128-288 288c0 108.8 57.6 201.6 147.2 249.6-121.6 48-214.4 153.6-240 288-3.2 9.6 0 19.2 6.4 25.6 3.2 9.6 12.8 12.8 22.4 12.8h704c9.6 0 19.2-3.2 25.6-12.8 6.4-6.4 9.6-16 6.4-25.6-25.6-134.4-121.6-240-243.2-288z"></path></svg><span><a class="author-item" href="http://www.daijiyong.cn" target="_blank" rel="noopener noreferrer">Mr.Dai</a></span><span property="author" content="Mr.Dai"></span></span><!----><span class="date-info" aria-label="写作日期📅" data-balloon-pos="down" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon calendar-icon" viewbox="0 0 1024 1024" fill="currentColor" aria-label="calendar icon"><path d="M716.4 110.137c0-18.753-14.72-33.473-33.472-33.473-18.753 0-33.473 14.72-33.473 33.473v33.473h66.993v-33.473zm-334.87 0c0-18.753-14.72-33.473-33.473-33.473s-33.52 14.72-33.52 33.473v33.473h66.993v-33.473zm468.81 33.52H716.4v100.465c0 18.753-14.72 33.473-33.472 33.473a33.145 33.145 0 01-33.473-33.473V143.657H381.53v100.465c0 18.753-14.72 33.473-33.473 33.473a33.145 33.145 0 01-33.473-33.473V143.657H180.6A134.314 134.314 0 0046.66 277.595v535.756A134.314 134.314 0 00180.6 947.289h669.74a134.36 134.36 0 00133.94-133.938V277.595a134.314 134.314 0 00-133.94-133.938zm33.473 267.877H147.126a33.145 33.145 0 01-33.473-33.473c0-18.752 14.72-33.473 33.473-33.473h736.687c18.752 0 33.472 14.72 33.472 33.473a33.145 33.145 0 01-33.472 33.473z"></path></svg><span>2021年11月15日</span><meta property="datePublished" content="2021-11-15T00:00:00.000Z"></span><span class="category-info" aria-label="分类🌈" data-balloon-pos="down" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon category-icon" viewbox="0 0 1024 1024" fill="currentColor" aria-label="category icon"><path d="M148.41 106.992h282.176c22.263 0 40.31 18.048 40.31 40.31V429.48c0 22.263-18.047 40.31-40.31 40.31H148.41c-22.263 0-40.311-18.047-40.311-40.31V147.302c0-22.263 18.048-40.31 40.311-40.31zM147.556 553.478H429.73c22.263 0 40.311 18.048 40.311 40.31v282.176c0 22.263-18.048 40.312-40.31 40.312H147.555c-22.263 0-40.311-18.049-40.311-40.312V593.79c0-22.263 18.048-40.311 40.31-40.311zM593.927 106.992h282.176c22.263 0 40.31 18.048 40.31 40.31V429.48c0 22.263-18.047 40.31-40.31 40.31H593.927c-22.263 0-40.311-18.047-40.311-40.31V147.302c0-22.263 18.048-40.31 40.31-40.31zM730.22 920.502H623.926c-40.925 0-74.22-33.388-74.22-74.425V623.992c0-41.038 33.387-74.424 74.425-74.424h222.085c41.038 0 74.424 33.226 74.424 74.067v114.233c0 10.244-8.304 18.548-18.547 18.548s-18.548-8.304-18.548-18.548V623.635c0-20.388-16.746-36.974-37.33-36.974H624.13c-20.585 0-37.331 16.747-37.331 37.33v222.086c0 20.585 16.654 37.331 37.126 37.331H730.22c10.243 0 18.547 8.304 18.547 18.547 0 10.244-8.304 18.547-18.547 18.547z"></path></svg><ul class="categories-wrapper"><li class="category category4 clickable" role="navigation">做做算法</li><meta property="articleSection" content="做做算法"></ul></span><span aria-label="标签🏷" data-balloon-pos="down" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon tag-icon" viewbox="0 0 1024 1024" fill="currentColor" aria-label="tag icon"><path d="M939.902 458.563L910.17 144.567c-1.507-16.272-14.465-29.13-30.737-30.737L565.438 84.098h-.402c-3.215 0-5.726 1.005-7.634 2.913l-470.39 470.39a10.004 10.004 0 000 14.164l365.423 365.424c1.909 1.908 4.42 2.913 7.132 2.913s5.223-1.005 7.132-2.913l470.39-470.39c2.01-2.11 3.014-5.023 2.813-8.036zm-240.067-72.121c-35.458 0-64.286-28.828-64.286-64.286s28.828-64.285 64.286-64.285 64.286 28.828 64.286 64.285-28.829 64.286-64.286 64.286z"></path></svg><ul class="tags-wrapper"><li class="tag tag6 clickable" role="navigation">算法</li></ul><meta property="keywords" content="算法"></span><span class="reading-time-info" aria-label="阅读时间⌛" data-balloon-pos="down" isoriginal="false" pageview="false"><svg xmlns="http://www.w3.org/2000/svg" class="icon timer-icon" viewbox="0 0 1024 1024" fill="currentColor" aria-label="timer icon"><path d="M799.387 122.15c4.402-2.978 7.38-7.897 7.38-13.463v-1.165c0-8.933-7.38-16.312-16.312-16.312H256.33c-8.933 0-16.311 7.38-16.311 16.312v1.165c0 5.825 2.977 10.874 7.637 13.592 4.143 194.44 97.22 354.963 220.201 392.763-122.204 37.542-214.893 196.511-220.2 389.397-4.661 5.049-7.638 11.651-7.638 19.03v5.825h566.49v-5.825c0-7.379-2.849-13.981-7.509-18.9-5.049-193.016-97.867-351.985-220.2-389.527 123.24-37.67 216.446-198.453 220.588-392.892zM531.16 450.445v352.632c117.674 1.553 211.787 40.778 211.787 88.676H304.097c0-48.286 95.149-87.382 213.728-88.676V450.445c-93.077-3.107-167.901-81.297-167.901-177.093 0-8.803 6.99-15.793 15.793-15.793 8.803 0 15.794 6.99 15.794 15.793 0 80.261 63.69 145.635 142.01 145.635s142.011-65.374 142.011-145.635c0-8.803 6.99-15.793 15.794-15.793s15.793 6.99 15.793 15.793c0 95.019-73.789 172.82-165.96 177.093z"></path></svg><span>大约 3 分钟</span><meta property="timeRequired" content="PT3M"></span></div><hr></div><div class="toc-place-holder"><aside id="toc"><div class="toc-header">此页内容</div><div class="toc-wrapper"><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/tech/algorithm/cut_wood.html#问题1" class="router-link-active router-link-exact-active toc-link level2">问题1</a></li><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/tech/algorithm/cut_wood.html#解题思路" class="router-link-active router-link-exact-active toc-link level3">解题思路</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/tech/algorithm/cut_wood.html#代码实现" class="router-link-active router-link-exact-active toc-link level3">代码实现</a></li><!----><!--]--></ul><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/tech/algorithm/cut_wood.html#问题2" class="router-link-active router-link-exact-active toc-link level2">问题2</a></li><ul class="toc-list"><!--[--><li class="toc-item"><a aria-current="page" href="/tech/algorithm/cut_wood.html#解题思路-1" class="router-link-active router-link-exact-active toc-link level3">解题思路</a></li><!----><!--]--><!--[--><li class="toc-item"><a aria-current="page" href="/tech/algorithm/cut_wood.html#代码实现-1" class="router-link-active router-link-exact-active toc-link level3">代码实现</a></li><!----><!--]--></ul><!--]--></ul></div></aside></div><!----><div class="theme-hope-content"><h2 id="问题1" tabindex="-1"><a class="header-anchor" href="#问题1" aria-hidden="true">#</a> 问题1</h2><p><img src="https://img-blog.csdnimg.cn/img_convert/685a6e9f87ddbf8f2ef4c62c2a4f1954.png" alt="图片" loading="lazy"></p><ul><li><p>有这么一组木头（用数组int[]表示），木头长度&gt;=1且长短不一</p></li><li><p>木头只能切短、不能拼接</p></li><li><p>给定一个要求的木头长度len和一组木头woods，要求将woods切成长度均为len的木头，请问最多能切出多少根？</p></li></ul><h3 id="解题思路" tabindex="-1"><a class="header-anchor" href="#解题思路" aria-hidden="true">#</a> 解题思路</h3><p>题目不难，因为只能切短不能拼接，所以直接循环遍历woods，分别将每根木头切成要求的长度</p><p>叠加每根木头能切出的要求长度木头的数量，即可求解</p><h3 id="代码实现" tabindex="-1"><a class="header-anchor" href="#代码实现" aria-hidden="true">#</a> 代码实现</h3><div class="language-text ext-text line-numbers-mode"><pre class="language-text"><code>public static Integer cutWoods2SpecifyLen(int[] woods, int len) {
        if (woods == null || woods.length == 0) {
            return 0;
        }
        int result = 0;
        for (int wood : woods) {
            result += wood / len;
        }
        return result;
    }
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>时间复杂度O(n)</p><p>空间复杂度O(1)</p><p>测试验证一下</p><div class="language-text ext-text line-numbers-mode"><pre class="language-text"><code>    public static void main(String[] args) {
        int[] woods = {100, 110, 50, 60, 100, 90};
        int specifyLen = 30;
        System.out.println(Arrays.toString(woods));
        System.out.printf(&quot;给定一组木头，要求切成%d长度，最多能切成%d根%n&quot;, specifyLen, cutWoods2SpecifyLen(woods, specifyLen));
    }
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><img src="https://img-blog.csdnimg.cn/img_convert/cc7a6a511cd357cf975f1c6baf6da7aa.png" alt="图片" loading="lazy"></p><h2 id="问题2" tabindex="-1"><a class="header-anchor" href="#问题2" aria-hidden="true">#</a> 问题2</h2><ul><li><p>问题1是要求给定要求的长度，求能切成多少段等长的木头</p></li><li><p>进阶一下，如果给定需要的等长木头的数量，求切出木头的最长长度呢？</p></li></ul><p><img src="https://img-blog.csdnimg.cn/img_convert/54bc11208f830b9bc4c5f45c30522155.png" alt="图片" loading="lazy"></p><p>如上图，给定一组木头，要求切出9根等长的木头，求能满足条件木头的最长的长度？</p><h3 id="解题思路-1" tabindex="-1"><a class="header-anchor" href="#解题思路-1" aria-hidden="true">#</a> 解题思路</h3><p>首先，这道题中其实一共有两个变量：切除木头的长度len、最终切出的木头根数num</p><p>并且这两个变量之间是相互制约的关系，此消彼长</p><p>如果len大，则num必然会变小</p><p>反之，则num必然会变大</p><p>num的大小同样也会影响len大小，同样成反比</p><p>那么我们就可以考虑先固定其中一个变量，然后就能求出另外一个变量了</p><p>其次我们应该思考，能满足要求的木头长度的范围</p><p>最短肯定是1，这种情况下木头可以切成100+110+50+60+100+90=510根</p><p>510&gt;9，满足条件</p><p><img src="https://img-blog.csdnimg.cn/img_convert/a048ef0871cbbece47b1ab6cf0f73b33.png" alt="图片" loading="lazy"></p><p>易知这组木头中最长的长度是max=110，</p><p>这种情况下能切出满足条件的木头根数是1</p><p>1&lt;9，不满足条件</p><p>所以题目要求的范围必定是在（1，110）范围内</p><p>那么我们现在就是需要在（1，110）这个范围内找到那个合适的值</p><p>一个增序的连续区间，要找到目标值，应该用什么办法呢？</p><p>很明显：<strong>二分法</strong>嘛</p><p>所以这道题的解题思路就是在（1，110）范围内使用二分查找</p><p>在指定能切出的最大木头长度len的情况下，判断得出的nums是否满足条件（nums&gt;=9）</p><p>从而求出最大的nums</p><h3 id="代码实现-1" tabindex="-1"><a class="header-anchor" href="#代码实现-1" aria-hidden="true">#</a> 代码实现</h3><div class="language-text ext-text line-numbers-mode"><pre class="language-text"><code>public static Integer cutWoods2SpecifyNum(int[] woods, int num) {
        if (woods == null || woods.length == 0) {
            return 0;
        }
        int result = 0;
        int min = 1;
        int max = getMaxLen(woods);
        while (min + 1 &lt; max) {
            result = (min + max) / 2;
            // 计算在给定长度result的情况，能够切出几根
            int numTemp = cutWoods2SpecifyLen(woods, result);
            if (numTemp &gt;= num) {
                min = result;
            } else {
                max = result;
            }
        }
        if (cutWoods2SpecifyLen(woods, max) &gt;= num) {
            return max;
        }
        if (cutWoods2SpecifyLen(woods, min) &gt;= num) {
            return min;
        }

        return result;
    }

    private static int getMaxLen(int[] woods) {
        int result = woods[0];
        for (int i = 1; i &lt; woods.length; i++) {
            if (woods[i] &gt; result) {
                result = woods[i];
            }
        }
        return result;
    }
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>时间复杂度O(l*logmax)，l为woods的数量，max为woods中最长木头的长度</p><p>空间复杂度O(1)</p><p>可能有些人会觉得这个二分实现有点别扭</p><p>这是我从一位大牛那里学到的一个二分法通用公式</p><p>容易理解而且容易掌握，有兴趣的话我回头可以专门写一篇博客讲讲这个二分模板代码</p><p>测试验证一下</p><p>没有问题</p><div class="language-text ext-text line-numbers-mode"><pre class="language-text"><code>    public static void main(String[] args) {
        int[] woods = {100, 110, 50, 60, 100, 90};
        int specifyNum = 9;
        System.out.println(Arrays.toString(woods));
        System.out.printf(&quot;给定一组木头，要求切成等长的%d跟，能得到的最长长度为%d%n&quot;, specifyNum, cutWoods2SpecifyNum(woods, specifyNum));
    }
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><img src="https://img-blog.csdnimg.cn/img_convert/14c532d3e6348053ca1473f0cf5ad14b.png" alt="图片" loading="lazy"></p><div style="text-align:right;"><p>文/戴先生@2021年11月15日</p></div></div><!----><footer class="page-meta"><!----><div class="meta-item update-time"><span class="label">上次编辑于: </span><span class="info">2022/6/4 21:27:52</span></div><div class="meta-item contributors"><span class="label">贡献者: </span><!--[--><!--[--><span class="contributor" title="email: daijiyong.p@qq.com">daijiyong</span><!--]--><!--]--></div></footer><nav class="page-nav"><a href="/tech/algorithm/search-in-rotated-sorted-array.html" class="nav-link prev" aria-label="必会算法：在旋转有序的数组中搜索"><div class="hint"><span class="arrow left"></span>上一页</div><div class="link"><!---->必会算法：在旋转有序的数组中搜索</div></a><!----></nav><!----><!----><!--]--></main><!--]--><footer class="footer-wrapper"><div class="footer"></div><div class="copyright">Copyright © 2022 Mr.Dai</div></footer><!--]--></div><!--]--><!----><!--]--></div>
    <script type="module" src="/assets/app.cfbcad7e.js" defer></script>
  </body>
</html>
